2674. Сокращение дроби

Сократите заданную дробь.

Вход. Числитель и знаменатель дроби (целые числа, по модулю не превышают 10⁹).

Выход. Вывести числитель и знаменатель сокращенной дроби.

Пример входа 1	Пример выхода 1
2 4	1 2
Пример входа 2	Пример выхода 2
-12 15	-4 5

РЕШЕНИЕ

НОД

Анализ алгоритма

Пусть n / m – заданная дробь. Вычислим d = НОД(|n|, |m|). Сокращенная дробь будет иметь вид (n / d) / (m / d).

Реализация алгоритма

Читаем входные данные.

scanf("%d %d",&n,&m);

Вычисляем наибольший общий делитель модулей числителя и знаменателя дроби.

d = gcd(abs(n),abs(m));

Сокращаем и выводим дробь.

printf("%d %d\n",n/d,m/d);

Java реализация

import java.util.*;

public class Main

{

static int gcd(int a, int b)

{

if (a == 0) return b;

if (b == 0) return a;

if (a >= b) return gcd(a % b, b);

return gcd(a, b % a);

}

public static void main ( String []args)

{

Scanner con = new Scanner (System.in);

int a = con.nextInt();

int b = con.nextInt();

int d = gcd(Math.abs(a),Math.abs(b));

System.out.println(a / d + " " + b / d);

con.close();

}

}